package com.yitau.sort;

import com.yitau.utils.ArrayUtils;

import java.util.Arrays;

/**
 * 归并排序
 */
public class MergeSort {

    /**
     * 1. 将数组划分为两个子数组 A,B 直到其不可划分
     * 2. 将 A,B 通过归并排序使其有序
     * 3. 合并两个有序数组
     * @param array 原数组，执行完后数组内容改变
     * @param begin 需要排序数组的起始位置
     * @param end 需要排序数组的结束位置
     */
    public static void mergeSort(int[] array, int begin, int end) {
        if (begin < end) {
            int mid = (begin + end) / 2;
            mergeSort(array, begin, mid);
            mergeSort(array, mid + 1, end);
            merge(array, begin, mid, end);
        }
    }

    /**
     * 将数组的两个子数组进行归并操作，默认两个子数组已经有序
     * @param array 原数组
     * @param begin 需要归并数组的起始位置
     * @param mid 需要归并数组的两个子数组分割位置
     * @param end 需要归并数组的结束位置
     */
    public static void merge(int[] array, int begin, int mid, int end) {
        // 两个子数组
        int[] arrayA = Arrays.copyOfRange(array, begin, mid + 1);
        int[] arrayB = Arrays.copyOfRange(array, mid + 1, end + 1);
        // 将 A,B 两个子数组按照顺序重新归并到原数组
        // 通过遍历方式
        int i = 0;
        int j = 0;
        int k = begin;
        while (i < arrayA.length && j < arrayB.length && k < end) {
            if (arrayA[i] <= arrayB[j]) {
                array[k++] = arrayA[i++];
            } else {
                array[k++] = arrayB[j++];
            }
        }
        // 继续遍历完子数组
        while (i < arrayA.length) {
            array[k++] = arrayA[i++];
        }
        while (j < arrayB.length) {
            array[k++] = arrayB[j++];
        }
    }



    public static void mergeSort(int[] array) {
        System.out.print("排序前：");
        ArrayUtils.printArray(array);
        mergeSort(array, 0, array.length - 1);
        System.out.print("排序后：");
        ArrayUtils.printArray(array);
    }

    public static void main(String[] args) {
        // write your code here
        System.out.println("正序：");
        mergeSort(ArrayUtils.DEFAULT_ARRAY_ASC);
        System.out.println("逆序：");
        mergeSort(ArrayUtils.DEFAULT_ARRAY_DESC);
        System.out.println("随机：");
        mergeSort(ArrayUtils.DEFAULT_ARRAY_RANDOM);
    }
}
